struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *cur_node = new ListNode();
        ListNode *head = cur_node;
        while (list1 != nullptr || list2 != nullptr)
        {
            if (list1->val < list2->val)
            {
                ListNode *next_node1 = new ListNode();
                next_node1->val = list1->val;
                cur_node->next = next_node1;
                cur_node = cur_node->next;
                list1 = list1->next;
            }
            else if (list1->val == list2->val)
            {
                ListNode *next_node1 = new ListNode();
                next_node1->val = list1->val; // 这样是深拷贝
                cur_node->next = next_node1;  // 这样是浅拷贝
                cur_node = cur_node->next;
                list1 = list1->next;
                ListNode *next_node2 = new ListNode();
                next_node2->val = list2->val;
                cur_node->next = next_node2;
                cur_node = cur_node->next;
                list2 = list2->next;
            }
            else
            {
                ListNode *next_node2 = new ListNode();
                next_node2->val = list2->val;
                cur_node->next = next_node2;
                cur_node = cur_node->next;
                list2 = list2->next;
            }
        }
        return head->next;
    }
};

#include <iostream>
using namespace std;
int main()
{
    ListNode *list1 = new ListNode(1);
    ListNode *head1 = list1;
    list1->next = new ListNode(2);
    list1 = list1->next;
    list1->next = new ListNode(4);

    ListNode *list2 = new ListNode(1);
    ListNode *head2 = list2;
    list2->next = new ListNode(3);
    list2 = list2->next;
    list2->next = new ListNode(4);

    Solution test;
    ListNode *res = test.mergeTwoLists(head1, head2);

    while (res->next != nullptr)
    {
        cout << res->val;
        res = res->next;
    }

    // ListNode *cur_node = head1;
    // for (size_t i = 0; i < 3; i++)
    // {
    //     // 释放链表空间
    //     cout << cur_node->val;
    //     head1 = head1->next;
    //     free(cur_node);
    //     cur_node = head1;
    // }
}